\section*{Введение}
\addcontentsline{toc}{section}{\tocsecindent{Введение}}
\subsection*{Что такое геном}

\textit{Геном} --- это полная совокупность наследственной информации организма. Обычно она закодирована в молекулах дезоксирибонуклеиновой кислоты (ДНК). Она определяет полный жизненный цикл организма.

Молекула ДНК состоит из двух линейных длинных полимеров, называемых \textit{стрендами}, состоящих из более простых молекул, называемых \textit{нуклеотидами} или \textit{основаниями}. Есть всего четыре различных оснований: аденин (A), цитозин (C), гуанин (G) и тимин (T). Два стренда расположены близко друг к другу и закручены в двойную спираль. Химическая структура стренда несимметрична, поэтому можно формально определить его направление. В молекуле ДНК стренды антипараллельны: 
нуклеотиды располагаются один напротив другого, а направления стрендов противоположны. Оказывается, что зная конкретный нуклеотид (тип основания) на одном стренде можно сказать какой будет на соответствующем месте другого стренда. Этот факт носит название \textit{комплементарной парности оснований}. A находится только напротив T, а C --- напротив G.

Подытоживая вышесказанное, если мы выпишем стренды ДНК как две длинные строки в четырех буквенном алфавите с учетом направления, то они окажутся реверс-комплементарными (в дальнейшем объекты, находящиеся в этом отношении будем называть \textit{сопряженными}) друг другу: если прочитать одну из них от конца к началу, заменяя каждый нуклеотид комплементарным, получится вторая.

Внутри клетки молекулы ДНК организуются в более сложные структуры, называемые \textit{хромосомами}.

Длиной генома будем считать суммарную длину всех хромосом.

Для простоты везде далее (если не сделано специальных оговорок) считается, что весь геном заключен в одной единственной хромосоме (молекуле ДНК). 

Помимо здорового интереса, у проектов по выявлению конкретной последовательности ДНК %геномики (раздела молекулярной генетики, посвященного изучению генома) 
есть огромное количество областей применения. В них, например, входят: 
\begin{itemize}
\item персональная медицина (диагностика генетических заболеваний)
\item поиск и производство новых антибиотиков
\item выявление эволюционных закономерностей и степеней родства между организмами
\item анализ генов и генная инженерия
\end{itemize}

\subsection*{Секвенирование ДНК и сборка из фрагментов}

Технология, позволившая бы "прочитать" длинный (длиннее 10 тыс. оснований) участок генома нуклеотид за нуклеотидом остается неизвестной. Но были разработаны технологии, работающие в обход этого ограничения. Идея состоит в генерации огромного количества сравнительно коротких фрагментов из большого числа копий одного и того же генома и разгадывании получившейся гигантской головоломки из перекрывающихся элементов.

Таким образом, проблема восстановления последовательности нуклеотидов ДНК в подавляющем большинстве случаев сводится к генерации фрагментов (биологическая задача) и реконструкции по ним исходной последовательности (вычислительная задача).

Процесс генерации фрагментов называется \textit{секвенированием}. Аппараты, осуществляющие этото процесс называют \textit{секвенаторами}.

Процесс реконструкции по ним исходной последовательности называется \textit{ассемблированием} или \textit{сборкой}. Как мы увидим в дальнейшем, сборка является очень сложной алгоритмической задачей, многие трудности, возникающие при решении которой, так и не преодолены. Програмные комплексы, осуществляющие сборку называют \textit{ассемблерами}.

Первую технологию секвенирования ДНК придумали в 1970-х, Уолтер Гилберт и Фред Сангер, получившие за это Нобелевскую премию. С помощью различных приемников этой технологии было секвенировано большое количество вирусных и бактериальных геномов. Но эти технологии были слишком медленными и дорогими. Проекты по секвенированию млекопитающих, таких как человек или мышь растягивались на годы и стоили миллионы долларов.

Начиная с 2000 года все большее распространения начали получать технологии, объединенные под общим названием технологий секвенирования \textit{следующего поколения} (NGS, Next Generation Sequencing technologies). Они позволили снизить стоимость и время секвенирования в сотни раз. Но при этом, если длина фрагментов при использовании классических технологий, могла достигать 1000 нуклеотидов, то наиболее популярные \footnote{Наиболее популярными на сегодняшний день являются секвенаторы фирмы Illumina} из NGS технологий даже и сегодня, по прошествии десяти лет, предоставляют фрагменты длина которых всего $100-200$ нуклеотидов.

Переход на NGS технологии значительно усложнил задачу сборки и сделал существовавшие ранее подходы просто-напросто неприменимыми.

На самом деле, в области ассемблирования есть две различные задачи:
\begin{itemize}
\item сборка при наличии ранее восстановленного генома особи того же вида, что и исследуемая (reference genome)
%(difference between two individuals is usually no more than $0.2$\%???).
\item \textit{de novo} сборка, когда таковой отсутствует
\end{itemize}

Везде далее в данной работе идет речь именно о подходах к \textit{de novo} сборке.

Павел Певзнер с соавторами (\cite{CP10}) предложил следующую метафору. Восстановление генома похоже на подрыв ящика, в котором находились экземпляры сегодняшнего номера газеты ``Times'' и последующую попытку восстановления содержания газеты по получившимся кусочкам. Некоторые участки конкретного экземпляра могли быть полностью уничножены взрывом, а кусочки разных газет будут перекрываться и содержать одни и те же участки текста.

Но хотя задача сборки генома по постановке и похожа на восстановление газеты по клочкам, на самом деле она значительно сложнее. И дело не только в том, что для достижения приемлемого результата при восстановлении, скажем, генома млекопитающего, приходится иметь дело с миллиардами фрагментов.

Во-первых, вспомним, что газета написана на некотором естественном языке, чьи правила могут подсказать нам взаимное расположение кусочков вне зависимости от того перекрываются они или нет. Правила ``языка'' ДНК все еще в основном не известны биологам, так что практически невозможно определить даже примерное взаимное расположение двух неперекрывающихся ридов. 

Во-вторых, ``алфавит'' нуклеотидов содержит всего четыре буквы (A, T, G, C). Это сильно усложняет задачу, так как большое количество наблюдаемых нами наложений произошли совершенно случайно и не соответствуют одному участку исходной последовательности. 

В-третьих, ДНК содержит большое количество последовательностей, повторенных в геноме большое количество раз, быть может, с небольшими изменениями. Такие участки называются \textit{повторами}. Например, так называемый повтор Alu, последовательность длины около $300$ нуклеотидов, встречается (с небольшими вариациями) в человеческом геноме миллион.

В-четвертых, даже самые современные методы секвенирования не идеальны и получающиеся фрагменты содержат большое количество ошибок, попадание которых в итоговую сборку крайне нежелательно. 

И наконец, большинство современных технологий секвенирования имеют возможность генерации не только одиночных, но и парных фрагментов, причем расстояние в геноме между фрагментами, принадлежащими одной паре считается известным. Правильное использование этой дополнительной ``парной'' информации, как мы увидим в дальнейшем, может значительно повысить качество итоговой сборки, но является весьма непростой задачей, универсального метода для решения которой не существует.

Таким образом, задача сборки генома по коротким фрагментам является одной из наиболее важных и алгоритмически трудных задач в биоинформатике. 
Несмотря на то, что за последние 20 лет ей занимались сотни исследователей и были реализованы десятки ассемблеров, в ней и по сей день остается огромное количество нерешенных проблем. 

\subsection*{О теоретической сложности задачи ассемблирования}
Задача ассемблера состоит в нахождении строки ДНК, наиболее хорошо согласованной с данными ему на вход фрагментами. Далее в этом разделе предполагается, что данные сгенерированы без ошибок, что является очень серьезным упрощением решаемой задачи.

Как уже упоминалось, объемы входных данных для алгоритма, огромны. Ассемблерам, работающим с фрагментами, полученными по NGS технологиям приходится обрабатывать миллионы и миллиарды (если речь о сборке генома млекопитающего) фрагментов.

В таких условиях первостепенным является вопрос об асимптотике применяемого алгоритма. Квадратичный (от размера входных данных) алгоритм, даже с чрезвычайно малой константой уже оказывается более чем сомнительным. Об алгоритмах с экспоненциальным временем работы не следует и помышлять.

В связи с вышесказанным, возникает вопрос о классификации решаемой задачи с точки зрения теории сложности.

Обычно, говоря о формальной постановке, задачу ассемблирования переформулируют как известную задачу о \textit{кратчайшей общей надстроке} (SSP, Shortest Superstring Problem) для множества входных фрагментов.

Задача о кратчайшей общей надстроке \cite{superstring} формулируется следующим образом:
\\\b{Вход.} Набор строк $\{s_1, s_2, \dots, s_n\}$ и натуральное число $m$.
\\\b{Вопрос.} Существует ли строка $t$, состоящая из не более чем $m$ символов,
такая что каждая строка $s_i$ является подстрокой $t$?

Естественно, на практике более полезна данная задача в формулировке не
<<Существует ли строка...?>>, а <<Найти кратчайшую строку, которая...>>.
Однако именно в приведенной формулировке задача является вопросом с ответом
да/нет, и потому можно говорить о ее классификации в рамках теории сложности.

Если не делать никаких дополнительных предположений, то задача SSP является NP-полной \cite{gusfield}. Из этого следует, что
не только ответ на вопрос о существовании, но и поиск самой кратчайшей строки
невозможно осуществить за полиномиальное время, если только не выполняется $P = NP$.

Обычно современным ассемблерам приходится иметь дело с парными фрагментами.
В работе \cite{DV10} задача SSP была расширена на множество парных фрагментов, которые в итоговой строке должны находиться в фиксированном диапазоне расстояний друг от друга и показано, что в отсутствии дополнительных предположений, эта задача также NP-полна. 

Получается, что найти точное решение задачи ассемблирования в такой постановке оказывается невозможно, так как на существование полиномиального алгоритма рассчитывать не приходится.